SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Iterated binary operation</title>

</head>

Iterated binary operation

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, an iterated binary operation is an extension of a <a href="Binary_operation" title="Binary operation">binary operation</a> on a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> S to a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> on finite <a href="Sequence" title="Sequence">sequences</a> of elements of S through repeated application.<a href="#cite_note-IBO1-1">[1]</a> Common examples include the extension of the <a href="Addition" title="Addition">addition</a> operation to the <a href="Summation" title="Summation">summation</a> operation, and the extension of the <a href="Multiplication" title="Multiplication">multiplication</a> operation to the <a href="Product_(mathematics)" title="Product (mathematics)">product</a> operation. Other operations, e.g., the set-theoretic operations <a href="Union_(set_theory)" title="Union (set theory)">union</a> and <a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a>, are also often <a href="Iterated" class="mw-redirect" title="Iterated">iterated</a>, but the iterations are not given separate names. In print, summation and product are represented by special symbols; but other iterated operators often are denoted by larger variants of the symbol for the ordinary binary operator. Thus, the iterations of the four operations mentioned above are denoted

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum ,\ \prod ,\ \bigcup ,}</annotation>

</semantics>

</math><img src="./def92a214c1e191ac3c72201eb29d2acc2ff11c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:13.556ex; height:3.843ex;" alt="{\displaystyle \sum ,\ \prod ,\ \bigcup ,}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigcap }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \bigcap }</annotation>

</semantics>

</math><img src="./c0adfc18fcdbe3b7df28d94884ec24ca3ecc937b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:2.582ex; height:3.843ex;" alt="{\displaystyle \bigcap }" loading="lazy">, respectively.</dd></dl>

More generally, iteration of a binary function is generally denoted by a slash: iteration of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> over the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},a_{2}\ldots ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},a_{2}\ldots ,a_{n})}</annotation>

</semantics>

</math><img src="./629cd7d64778f0c473a2123a6ea17ee62b0fef40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.391ex; height:2.843ex;" alt="{\displaystyle (a_{1},a_{2}\ldots ,a_{n})}" loading="lazy"> is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}</annotation>

</semantics>

</math><img src="./36c50800d59d2cafc337f4cb6241aad8bae82c7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.832ex; height:2.843ex;" alt="{\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}" loading="lazy">, following the notation for <a href="Fold_(higher-order_function)" title="Fold (higher-order function)">reduce</a> in <a href="Bird%E2%80%93Meertens_formalism" title="Bird–Meertens formalism">Bird–Meertens formalism</a>.

In general, there is more than one way to extend a binary operation to operate on finite sequences, depending on whether the operator is <a href="Associative" class="mw-redirect" title="Associative">associative</a>, and whether the operator has <a href="Identity_element" title="Identity element">identity elements</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Denote by aj,k, with j ≥ 0 and k ≥ j, the finite sequence of length k − j of elements of S, with members (ai), for j ≤ i < k. Note that if k = j, the sequence is empty.

For f : S × S → S, define a new function Fl on finite nonempty sequences of elements of S, where

<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}}</annotation>

</semantics>

</math>

Similarly, define

<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}}</annotation>

</semantics>

</math>

If f has a unique left identity e, the definition of Fl can be modified to operate on empty sequences by defining the value of Fl on an empty sequence to be e (the previous base case on sequences of length 1 becomes redundant). Similarly, Fr can be modified to operate on empty sequences if f has a unique right identity.

If f is associative, then Fl equals Fr, and we can simply write F. Moreover, if an identity element e exists, then it is unique (see <a href="Monoid" title="Monoid">Monoid</a>).

If f is <a href="Commutative" class="mw-redirect" title="Commutative">commutative</a> and associative, then F can operate on any non-empty finite <a href="Multiset" title="Multiset">multiset</a> by applying it to an arbitrary enumeration of the multiset. If f moreover has an identity element e, then this is defined to be the value of F on an empty multiset. If f is idempotent, then the above definitions can be extended to <a href="Finite_set" title="Finite set">finite sets</a>.

If S also is equipped with a <a href="Metric_(mathematics)" class="mw-redirect" title="Metric (mathematics)">metric</a> or more generally with <a href="Topology" title="Topology">topology</a> that is <a href="Hausdorff_space" title="Hausdorff space">Hausdorff</a>, so that the concept of a <a href="Limit_of_a_sequence" title="Limit of a sequence">limit of a sequence</a> is defined in S, then an <a href="Infinity" title="Infinity">infinite</a> iteration on a countable sequence in S is defined exactly when the corresponding sequence of finite iterations converges. Thus, e.g., if a0, a1, a2, a3, … is an infinite sequence of <a href="Real_number" title="Real number">real numbers</a>, then the <a href="Infinite_product" title="Infinite product">infinite product</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{i=0}^{\infty }a_{i}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{i=0}^{\infty }a_{i}}</annotation>

</semantics>

</math><img src="./e2128727eb5bce437d6f89ab84b40cc3afec2c0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.51ex; height:3.176ex;" alt="{\textstyle \prod _{i=0}^{\infty }a_{i}}" loading="lazy"> is defined, and equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}">

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}</annotation>

</semantics>

</math><img src="./ac339745b5614a95b72c75aa25fbe0d1aeabbd0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.817ex; height:4.009ex;" alt="{\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}" loading="lazy"> if and only if that limit exists.

<div class="mw-heading mw-heading2"><h2 id="Non-associative_binary_operation">Non-associative binary operation</h2></div>

The general, non-associative binary operation is given by a <a href="Magma_(algebra)" title="Magma (algebra)">magma</a>. The act of iterating on a non-associative binary operation may be represented as a <a href="Binary_tree" title="Binary tree">binary tree</a>.

<div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2></div>

Iterated binary operations are used to represent an operation that will be repeated over a set subject to some constraints. Typically the lower bound of a restriction is written under the symbol, and the upper bound over the symbol, though they may also be written as superscripts and subscripts in compact notation. Interpolation is performed over positive <a href="Integer" title="Integer">integers</a> from the lower to upper bound, to produce the set which will be substituted into the index (below denoted as i ) for the repeated operations.

Common notations include the big Sigma (<a href="Summation" title="Summation">repeated sum</a>) and big Pi (<a href="Product_(mathematics)" title="Product (mathematics)">repeated product</a>) notations.

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=0}^{n-1}i=0+1+2+\dots +(n-1)}</annotation>

</semantics>

</math>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{i=0}^{n-1}i=0\times 1\times 2\times \dots \times (n-1)}</annotation>

</semantics>

</math>

It is possible to specify set membership or other logical constraints in place of explicit indices, in order to implicitly specify which elements of a set shall be used:

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{x\in S}x=x_{1}+x_{2}+x_{3}+\dots +x_{n}}</annotation>

</semantics>

</math>

Multiple conditions may be written either joined with a <a href="Logical_and" class="mw-redirect" title="Logical and">logical and</a> or separately:

</mrow>

</mrow>

</munder>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{(i\in 2\mathbb {N} )\wedge (i\leq n)}i=\sum _{\stackrel {i\in 2\mathbb {N} }{i\leq n}}i=0+2+4+\dots +n}</annotation>

</semantics>

</math>

Less commonly, any <a href="Binary_operator" class="mw-redirect" title="Binary operator">binary operator</a> such as <a href="Exclusive_or" title="Exclusive or">exclusive or</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy">) or <a href="Set_union" class="mw-redirect" title="Set union">set union</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cup }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cup }</annotation>

</semantics>

</math><img src="./e8ff7d0293ad19b43524a133ae5129f3d71f2040.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \cup }" loading="lazy">) may also be used.<a href="#cite_note-2">[2]</a> For example, if S is a set of logical <a href="Proposition" title="Proposition">propositions</a>:

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \bigwedge _{p\in S}p=p_{1}\wedge p_{2}\wedge \dots \wedge p_{N}}</annotation>

</semantics>

</math>

which is true <a href="Iff" class="mw-redirect" title="Iff">iff</a> all of the elements of S are true.

<ul><li><a href="Unary_operation" title="Unary operation">Unary operation</a></li>

<li><a href="Unary_function" title="Unary function">Unary function</a></li>

<li><a href="Binary_operation" title="Binary operation">Binary operation</a></li>

<li><a href="Binary_function" title="Binary function">Binary function</a></li>

<li><a href="Ternary_operation" title="Ternary operation">Ternary operation</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSaunders_MacLane1971" class="citation book cs1">Saunders MacLane (1971). Categories for the Working Mathematician. New York: Springer-Verlag. p. 142. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0387900357</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFWeisstein" class="citation web cs1">Weisstein, Eric W. <a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/Union.html">"Union"</a>. mathworld.wolfram.com. Wolfram Mathworld. Retrieved 30 January 2018.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20071009181156/http://www.short-fuze.co.uk/~eddy/math/associate.html">Bulk action</a></li>

<li><a rel="nofollow" class="external text" href="http://wotug.ukc.ac.uk/parallel/acronyms/hpccgloss/P.html#parallel%20prefix">Parallel prefix operation</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20130603182033/http://wotug.ukc.ac.uk/parallel/acronyms/hpccgloss/P.html#parallel%20prefix">Archived</a> 2013-06-03 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.cornell.edu/Info/People/sfa/Nuprl/iterated_binops/Xiter_via_intseg_remark_INTRO.html">Nuprl iterated binary operations</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-07" href="https://en.wikipedia.org/wiki/?title=Iterated_binary_operation&oldid=1279251407">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>